#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
using namespace std;
/**
 * @brief
 * 1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.
 */
class Solution
{
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        int nums2Len = nums2.size();
        vector<int> ans;
        for (int n : nums1)
        {
            for (int i = 0; i < nums2Len; i++)
            {
                if (n == nums2[i])
                {
                    int j = i + 1;
                    bool find = false;
                    while (j < nums2Len)
                    {
                        if (nums2[j] > n)
                        {
                            ans.push_back(nums2[j]);
                            find = true;
                            break;
                        }
                        j++;
                    }
                    if (!find)
                    {
                        ans.push_back(-1);
                    }
                }
            }
        }

        return ans;
    }

    vector<int> nextGreaterElement_2(vector<int> &nums1, vector<int> &nums2)
    {

        // first solution worked but is slow
        // my thought process was to make a map where the key  is the element  of nums2 and the value is the index of that element in nums2
        //  we then iterate over nums1 use the map to get the index value of nums 2
        unordered_map<int, int> m;
        int nums1Len = nums1.size(), nums2Len = nums2.size();
        vector<int> res(nums1Len, -1);
        for (int i = 0; i < nums2Len; i++)
        {
            // key is the element and the element is the index
            m[nums2[i]] = i;
        }
        for (int i = 0; i < nums1Len; i++)
        {
            int index = m[nums1[i]];
            for (int k = index + 1; k < nums2Len; k++)
            {
                if (nums2[k] > nums1[i])
                {
                    res[i] = nums2[k];
                    break;
                }

                // // not find- deafult
                // if (k + 1 > nums2Len)
                // {
                //     res[i] = -1;
                //     break;
                // }
            }
        }
        return res;
    }

    vector<int> nextGreaterElement_3(vector<int> &nums1, vector<int> &nums2)
    {
        // Another solution is to use a stack and start iterating from the end of nums2 where the "previous number" is actually the next number and we check to see if that number is greater than the number we are currently at
        stack<int> s;
        unordered_map<int, int> m;
        vector<int> res;
        int nums1Len = nums1.size();
        int nums2Len = nums2.size();
        for (int i = nums2Len - 1; i >= 0; i--)
        {
            while (!s.empty() && nums2[i] > s.top())
            {
                // this "previous" number(next number)
                // is not actually greater than our current number so we pop it from the stack
                s.pop();
            }
            // this is the last element
            if (s.empty())
            {
                m[nums2[i]] = -1;
            }
            else
            {
                // for this element(key) we make the value the next greater element
                m[nums2[i]] = s.top();
            }
            s.push(nums2[i]);
        }
        for (int i = 0; i < nums1Len; i++)
        {
            res.push_back(m.at(nums1[i]));
        }
        return res;
    }
};
int main()
{
    /**
     * @brief
     * Test case
     * [1,3,5,2,4][6,5,4,3,2,1,7] ->[7,7,7,7,7]
     *
     */
    Solution s;
    vector<int> nums1 = {1, 3, 5, 2, 4}, nums2 = {6, 5, 4, 3, 2, 1, 7};

    vector<int> ans = s.nextGreaterElement_3(nums1, nums2);
    for (int a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}
